一个语法解析器必须能够判断在给定编程语法的情况下，用户编写的程序在语法上是否合理。通常，编程语法需要用某种形式来描述，下面给出形式化的定义：

Expr是我们的起始字符，Term、Factor是字符变量，num、name是我们的Token。对于每条规则，方便起见，顺序编了序号。现在看看我们根据定义的语法可以生成些什么？依次运用规则1->3->6->8->4->6->9->7->2->3->6->9->6->8,最终生成的表达式为4+a*(b-7)。这个过程可以使用语法生成树来表示：

解析与生成的过程相反：给定特定的sentence，我们需要构建出这棵语法生成树。根据构建过程可以将解析器分为两大类：

无论哪种解析方法，其中都涉及到替换规则的选择，不好的选择会对解析性能产生严重的影响，因此，合理高效的选择机制是解析算法的研究重点。

按照解析复杂度，我们可以把CFG(Context free grammar)分为4层：

任意CFG 没有限制条件的CFG，解析时间复杂度高达O(n^3)

LR(1) 这类解析器使用自底向上算法，从左向右解析，基于当前字符，每次朝前看至多一个token。

LL(1) 该类解析器是LR(1)的子集，使用自顶向下算法，从左向右解析，每次朝前看至多一个token。

RG Regular grammar是一类特殊的CFG，替换规则只有两种：A→aA\rightarrow aA→a或者A→aBA\rightarrow aBA→aB,其中a为终止字符，A、B为字符变量。

几乎所有的编程语言结构都能够使用LR(1)形式表达，LL(1)形式更为常见。

上面给出了一种通用地从顶向下的左替解析算法，root表示根节点，focus表示当前替换规则中最左边的字符，算法使用数据栈存储替换规则中待匹配的字符，word表示当前的输入字符。首先进行初始化工作，接着进入一个大循环：如果当前字符是可替换地，那么选择一条规则替换当前字符，将规则中待匹配的字符逆序压入栈中，更新focus；如果focus不可替换且匹配到了word，此时将输入字符序列下一字符读取到word中，弹出栈顶元素，更新focus；如果所有输入字符均已匹配，返回解析树，否则进行回溯操作。

回溯操作通常自底向上逐层进行：如果当前所有替换规则均替换失败，回溯到上一层，重新进行替换，如果回溯到顶层依然匹配失败，此时返回语法错误提示。回溯实际上是对整个语法结构的遍历，这会耗费大量时间，如果有某种算法可以避免回溯，这将大大提高解析性能。

将通用算法应用到我们本篇定义的表达式语法结构上，此时如果我们每次替换规则都选1，会发生什么事情呢？算法不会终止！这种现象称为Left-recursion。解决方法也很简单，我们可以重写语法替换规则，使得语法结构是Right-recursion即可：

显式Left-recursion消除可以使用以下方法：

Fee′→ϵFee'\rightarrow\epsilonFee′→ϵ的作用是终止替换，如果没有这条规则，Fee′→αFee′Fee'\rightarrow \alpha Fee'Fee′→αFee′就会不断循环下去。当然，除了直接显式的Left-recursion，还存在隐式Left-recursion，诸如α→β,β→γ,γ→αδ\alpha\rightarrow\beta,\beta\rightarrow\gamma,\gamma\rightarrow\alpha\deltaα→β,β→γ,γ→αδ,这最终会导致α→+αδ\alpha\rightarrow^+\alpha\deltaα→+αδ，下面给出一个消除Left-recursion的算法：

算法总体分为两步：首先将所有隐式Left-recursion转换为显式Left-recursion，接着消除显式Left-recursion。隐式Left-recursion可以从图的角度来理解：我们把所有具有Ai→AjγA_i\rightarrow A_j\gammaAi​→Aj​γ形式的替换规则表示成有向边，所有的字符变量当做图节点，那么隐式Left-recursion意味着图中有环，显然，隐式Left-recursion转换为显式Left-recursion的过程就是削减环的大小，直到图中只存在长度为1的环。

前面讲到，Top-down leftmost parser在解析时涉及回溯操作，这会降低解析性能。通过引入look-ahead技术，我们可以消解回溯，做到无回溯解析，对应地，这类语法叫做Backtrack-free grammar，也称作predictive grammar。在介绍无回溯解析算法前，先引入两个概念：First-set、Follow-set。

First-set 具有如下性质：

下面给出一个计算First-set的算法： 算法还是很直观地：首先计算终止字符的First-set，对于非终止字符来说，如果存在替换规则A→β,β=β1β2...βkA\rightarrow\beta,\beta=\beta_1\beta_2...\beta_kA→β,β=β1​β2​...βk​，那么First(A)⊇First(β1)First(A)\supseteq First(\beta_1)First(A)⊇First(β1​)。考虑β1\beta_1β1​包含ϵ\epsilonϵ的情况，此时First(A)⊇First(β2)First(A)\supseteq First(\beta_2)First(A)⊇First(β2​)，以此类推，直到计算完所有βi\beta_iβi​为止。

我们试着给出前面表达式语法的First set：

如果只使用First set，可能会出现一个问题：look-ahead字符不在First集合中怎么办，直接返回语法错误？这里的关键在于对ϵ\epsilonϵ的处理上，替换规则ϵ\epsilonϵ意思是跳过当前字符变量，转入其他替换规则中，但是从first-set的定义上可以看出，并不关心跳转操作，所以我们使用Follow-set来定义了跳转操作。下面给出计算Follow-set的算法：

有人可能有点迷糊：为啥这里只更新了Follow(β\betaβ),Follow(A)呢？这是因为A出现在替换规则的左边，我们无处得知与A所关联的结构信息，该信息只能从替换规则的右边获取。要想更新Follow(A),我们要找到如下规则：B→β1...A...βnB\rightarrow\beta_1...A...\beta_nB→β1​...A...βn​。 前面表达式语法的Follow set：

结合First set与Follow set，我们给出对于规则的First set定义：

对于任意的替换规则A→β1∣β2∣...∣βnA\rightarrow\beta_1|\beta_2|...|\beta_nA→β1​∣β2​∣...∣βn​，如果存在如下条件：

我们就说具有该规则的语法是backtrack-free的。基于此，引出两种Top-down解析算法：Recursive-Descent算法、Table-Driven算法。

Recursive-Descent的想法是朴素的：对于每个字符变量S，根据给出的语法结构，将其写成对应的一个递归函数，这样以来，我们就把Backtrack-free grammar转换为多个互相调用的递归函数组合，下面给出一个实现例子：